package jianzhiOffer;

public class num14_2 {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        long x = 3;
        long temp = 1;
        int b = n % 3;
        for(int a = n / 3 - 1;a > 0; a /= 2) {
            if(a % 2 == 1) temp = (temp * x) % 1000000007;
            x = (x * x) % 1000000007;
        }
        if(b == 0) return (int)(temp * 3 %1000000007);
        if(b == 1) return (int)(temp * 4 % 1000000007);
        return (int)(temp * 6 % 1000000007);
    }
}
